﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AlgorithmCenter
{
     public class AlgorithmCenter200911
     {
        private bool[,] Dp;
        /// <summary>
        /// 多重部分和问题
        /// dp[i,j] 是否能从前i个数据中找出和为j的 值义域（true-1,false-0）
        /// </summary>
        /// <param name="k"></param>
        /// <param name="a"></param>
        /// <param name="m"></param>
        /// <returns></returns>
        public bool MultiplePartialSum(int k,int[] a,int[] m)
        {
            Dp = new bool[a.Length+1,k+1];

            for (int i=1;i<=a.Length;i++)
            {
                for (int j=1;j<=k;j++)
                {
                    for (int t=0;t<=m[i-1];t++)
                    {
                        int temp=j - t * a[i - 1];
                        if (temp == 0)
                        {
                            Dp[i, j] = true;
                            break;
                        }
                        if (temp < 0)
                            break;
                        for (int z=1;z<=i-1;z++)
                        {
                            if (Dp[z,temp])
                            {
                                Dp[i, j] = true;
                            }
                        }
                    }
                }
            }
            return Dp[a.Length,k];
        }
     }
}
